#include <vector>
#include <string>
#include <functional>

using namespace std;

// 17. 电话号码的字母组合
class Solution 
{
private:
    const string letterMap[10] = 
    {
        "", "", "abc", "def", 
        "ghi", "jkl", "mno", 
        "pqrs", "tuv", "wxyz"
    };

public:
    vector<string> letterCombinations(string digits) 
    {
        int n = digits.size();
        if(n == 0) return {};

        vector<string> ret;
        string path;
        function<void(int)> dfs = [&](int index){
            if(index == n)
            {
                ret.push_back(path);
                return;
            }

            string letter = letterMap[digits[index] - '0'];
            for(int i = 0; i < letter.size(); ++i)
            {
                path += letter[i];
                dfs(index + 1);
                path.pop_back();
            }
        };

        dfs(0);
        return ret;
    }
};

class Solution 
{
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        vector<int> path;
        function<void(int)> dfs = [&](int index){
            if(index == n)
            {
                ret.push_back(path);
                return;
            }

            // 选当前元素
            path.push_back(nums[index]);
            dfs(index + 1);
            path.pop_back();

            // 不选当前元素
            dfs(index + 1);
        };

        dfs(0);
        return ret;
    }
};

// 131. 分割回文串
class Solution 
{
private:
    bool isPalindrome(const string& s, int begin, int end)
    {
        while(begin < end)
        {
            if(s[begin] != s[end]) return false;
            ++begin;
            --end;
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) 
    {
        int n = s.size();
        vector<vector<string>> ret;
        vector<string> path;
        
        function<void(int)> dfs = [&](int index){
            if(index == n)
            {
                ret.push_back(path);
                return;
            }

            for(int i = index; i < n; ++i)
            {
                if(isPalindrome(s, index, i))
                {
                    path.push_back(s.substr(index, i + 1 - index));
                    dfs(i + 1);
                    path.pop_back();
                }
            }
        };

        dfs(0);
        return ret;
    }
};

// 77. 组合
class Solution 
{
public:
    vector<vector<int>> combine(int n, int k) 
    {
        vector<vector<int>> ret;
        vector<int> path;

        function<void(int)> dfs = [&](int index){
            if(path.size() == k)
            {
                ret.push_back(path);
                return;
            }

            for(int i = index; i <= n; ++i)
            {
                path.push_back(i);
                dfs(i + 1);
                path.pop_back();
            }
        };

        dfs(1);
        return ret;
    }
};

// 216. 组合总和 III
class Solution 
{
public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        vector<vector<int>> ret;
        vector<int> path;
        function<void(int, int)> dfs = [&](int index, int sum){
            if(path.size() > k) return;
            if(path.size() == k)
            {
                if(sum == n) ret.push_back(path);
                return;
            }

            for(int i = index; i <= 9; ++i)
            {
                path.push_back(i);
                sum += i;
                dfs(i + 1, sum);
                path.pop_back();
                sum -= i;
            }
        };

        dfs(1, 0);
        return ret;
    }
};

// 22. 括号生成
class Solution 
{
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> ret;
        string path;
        int left = 0, right = 0;
        function<void()> dfs = [&](){
            if(right == n)
            {
                ret.push_back(path);
                return;
            }

            if(left < n)
            {
                path += '(';
                ++left;
                dfs();
                --left;
                path.pop_back();
            }

            if(right < left)
            {
                path += ')';
                ++right;
                dfs();
                --right;
                path.pop_back();
            }
        };  

        dfs();
        return ret;
    }
};

// 2855. 使数组成为递增数组的最少右移次数
class Solution 
{
public:
    int minimumRightShifts(vector<int>& nums) 
    {
        int n = nums.size(), i = 1;
        while(i < n && nums[i - 1] < nums[i]) ++i;
        if(i == n) return 0; // 只有一段递增
        // 至少两段
        if(nums[0] < nums[n - 1]) return -1;
        
        int mid = i; // 第二段的开始位置
        ++i;
        while(i < n && nums[i - 1] < nums[i]) ++i;
        if(i < n) return -1; // 至少三段
        return n - mid;
    }
};

// 979. 在二叉树中分配硬币
class Solution 
{
    int ret = 0;

    pair<int, int> dfs(TreeNode* node)
    {
        if(node == nullptr) return {0, 0};
        auto [coins_l, nodes_l] = dfs(node->left);
        auto [coins_r, nodes_r] = dfs(node->right);
        int coins = coins_l + coins_r + node->val;
        int nodes = nodes_l + nodes_r + 1;
        ret += abs(coins - nodes);
        return {coins, nodes};
    };

public:
    int distributeCoins(TreeNode* root) 
    {
        dfs(root);
        return ret;
    }
};


// 1856. 子数组最小乘积的最大值
class Solution 
{
    const int MOD = 1e9 + 7;

public:
    int maxSumMinProduct(vector<int>& nums) 
    {
        int n = nums.size();
        // 左边第一个小于，右边第一个小于等于
        vector<int> left(n), right(n, n);
        stack<int> st;
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && nums[st.top()] >= nums[i])
            {
                right[st.top()] = i;
                st.pop(); 
            }
            if(!st.empty()) left[i] = st.top() + 1;
            st.push(i);
        }

        vector<long long> prev(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            prev[i] = prev[i - 1] + nums[i - 1];
        }

        long long ret = 0;
        for(int i = 0; i < n; ++i)
        {
            ret = max(ret, (prev[right[i]] - prev[left[i]]) * nums[i]);
        }
        return ret % MOD;
    }
};